package 剑指offer_day02;

import java.util.HashMap;

/**
 * 剑指 Offer 35. 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * 详细题目描述看链接
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer35 {

    public Node copyRandomList(Node head) {

        if (head==null){
            return null;
        }

        //使用 循环遍历 从头到尾 遍历一次 链表 ， 使用map 记录新旧节点的对应关系

        Node corr = new Node(0);

        corr.next = head;

        HashMap<Node, Node> map = new HashMap<>();

        //第一次循环
        while (corr.next!=null){ //该节点不是空
            Node node = new Node(corr.next.val);
            map.put(corr.next,node);
            corr.next = corr.next.next;
        }

        corr.next = head;

        //第二次循环 将复制的节点 进行链接
        while (corr.next!=null){

            Node dNode = map.get(corr.next);

            dNode.next = map.get(corr.next.next);

            dNode.random = map.get(corr.next.random);

            corr.next = corr.next.next;

        }

        return map.get(head);

    }




    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(2);

        node1.next = node2;
        node1.random = node2;

        node2.random = node1;

        Offer35 offer35 = new Offer35();
        Node copyNode = offer35.copyRandomList(node1);



    }

}
